package com.demo.core.model.support.converter;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import com.demo.core.model.support.AdjacencyListModel;

import org.springframework.util.CollectionUtils;


/**
 * 链式对象转换器
 * 将邻接列表模型转换为链式对象
 * 
 * 此函数依赖数据库数据结构支撑
 * 提供效率较高的转换
 * @author ryuu.kk
 *
 */
public class AdjacencyListToChainedObjectConverter {
	
public static void main(String args[]) {
		
		AdjacencyListModel a = new AdjacencyListModel();
		List<AdjacencyListModel> list = new ArrayList<AdjacencyListModel>();
		
		a.setId(1L);
		a.setPid(null);
		list.add(a);
		
		a = new AdjacencyListModel();
		a.setId(2L);
		a.setPid(1L);
		list.add(a);
		
		a = new AdjacencyListModel();
		a.setId(3L);
		a.setPid(2L);
		list.add(a);
		
		a = new AdjacencyListModel();
		a.setId(4L);
		a.setPid(3L);
		list.add(a);
		
		a = new AdjacencyListModel();
		a.setId(5L);
		a.setPid(2L);
		list.add(a);
		
		a = new AdjacencyListModel();
		a.setId(6L);
		a.setPid(1L);
		list.add(a);
		
		a = new AdjacencyListModel();
		a.setId(7L);
		a.setPid(6L);
		list.add(a);
		
		a = new AdjacencyListModel();
		a.setId(8L);
		a.setPid(7L);
		list.add(a);
		
		a = new AdjacencyListModel();
		a.setId(9L);
		a.setPid(7L);
		list.add(a);
		
		AdjacencyListModel root = conver(list);
		
		System.out.print(root.leafCount());
	}
	
	/**
	 * 将邻接列表模型（数据结构调整后）转换为链式对象
	 * 由于数据结构调整,该函数的递归层级大为减少
	 * 并且list遍历一次将完成转换
	 * 
	 * @param list 邻接表模型
	 * @return 链式对象
	 */
	public static <T extends AdjacencyListModel> T conver(List<T> list) {
		
		if (CollectionUtils.isEmpty(list)) {
			return null;
		}
		Iterator<T> nodes = list.iterator();
		T root = nodes.next();
		next(null, root, nodes);
		return root;
	}
	/**
	 * 通过可能的父节点和当前节点查找树结构关系
	 * 当可能的父节点与当前节点不一致时
	 * 查找可能的父节点的父节点,并回溯到与当前节点相关的那个节点上
	 * 并且已该节点为可能的父节点再向下遍历
	 * 该方法不存在两个根节点的可能
	 * @param parent 可能的父节点
	 * @param child 当前节点
	 * @param nodes 邻接表
	 * @return 节点
	 */
	@SuppressWarnings("unchecked")
	private static <T extends AdjacencyListModel> T next(T parent, T child, Iterator<T> nodes) {
		
		if (parent == null) {
			child.setParent(parent);
		} else if (parent.getId().equals(child.getPid())) {
			child.setParent(parent);
			parent.addChild(child);
		} else {
			//数据结构支持,总是由根节点向下分布
			return next((T) parent.getParent(), child, nodes);
		}
		if (nodes.hasNext()) {
			return next(child, nodes.next(), nodes);
		}
		return null;
	}
}
